package com.base.dfs;

public class MaxAreaOfIsland {
    /**
     * 给定一个包含了一些 0 和 1 的非空二维数组 grid 。
     * <p>
     * 一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
     * <p>
     * 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/max-area-of-island
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    int[] xx = {0, 0, 1, -1};
    int[] yy = {1, -1, 0, 0};

    public int maxAreaOfIsland(int[][] area) {
        int maxArea = 0;
        for (int i = 0; i < area.length; i++) {
            for (int j = 0; j < area[i].length; j++) {
                int[] tmp = {0}; //注意参数的值，需要同步，所以这里用数组
                if (area[i][j] == 1) {
                    dfs(area, i, j, tmp);
                    maxArea = Math.max(maxArea, tmp[0]);
                }
            }
        }

        return maxArea;
    }

    public void dfs(int[][] area, int x, int y, int[] tmp) {
        tmp[0]++;//当前结点为1，所有要+1；
        area[x][y] = 0;//置零是防止重复计算
        for (int i = 0; i < 4; i++) {
            int xm = x + xx[i];
            int ym = y + yy[i];
            if (xm >= 0 && xm < area.length && ym >= 0 && ym < area[x].length && area[xm][ym] == 1) {
                dfs(area, xm, ym, tmp);
            }

        }


    }

    public void add(String x) {
        x = "dddd";
    }

    public static void main(String[] args) {
        MaxAreaOfIsland maxAreaOfIsland = new MaxAreaOfIsland();
        String x = "aaaa";
        maxAreaOfIsland.add(x);
        int[][] area = {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
        int maxarea = maxAreaOfIsland.maxAreaOfIsland(area);
        System.out.println(maxarea);

    }
}
